// 13.5 动态内存管理类
/**
 * 某些类需要在运行时分配可变大小的内存空间。这种类通常可以（并且如果它们确实可以的话，一般应该）使用标准库容器来保存它们的数据。
 * 例如，我们的StrBlob类使用一个vector来管理其元素的底层内存。
 * 但是，这一策略并不是对每个类都适用；某些类需要自己进行内存分配。这些类一般来说必须定义自己的拷贝控制成员来管理所分配的内存。
 */

#include <iterator>
#include <vector>
#include <list>
#include <deque>
#include <forward_list>
#include <string>
#include <array>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
using std::swap;
using std::vector, std::list, std::deque, std::forward_list, std::string, std::array, std::stack, std::queue;
#include "../Chapter07/Sales_data.h"
#include <iostream>
using std::begin, std::cbegin, std::end, std::cend, std::find, std::accumulate, std::equal, std::fill, std::fill_n, std::back_inserter;
using std::cin, std::cout, std::endl;
using std::copy, std::replace, std::replace_copy;
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <memory>
#include <new>
using namespace std;

// 类vector类内存分配策略的简化实现
class StrVec
{
public:
    StrVec &operator=(std::initializer_list<std::string>); // 赋值运算符重载
    // 非常量版本与常量版本下标运算符重载
    std::string& operator[](std::size_t n) { return elements[n]; }
    const std::string& operator[](std::size_t n) const { return elements[n]; } // 紧跟在参数列表后面的const表示this是一个指向常量的指针。像这样使用const的成员函数被称作常量成员函数（const member function）。

    StrVec(): // 默认构造函数（隐式地）默认初始化alloc并（显式地）将指针初始化为nullptr，表明没有元素。
        elements(nullptr), first_free(nullptr), cap(nullptr) {}
    StrVec(const StrVec&);            // 拷贝构造函数
    StrVec& operator=(const StrVec&); // 拷贝赋值运算符
    ~StrVec();                        // 析构函数
    void push_back(const std::string&); // 拷贝元素
    size_t size() const { return first_free - elements; }
    size_t capacity() const { return cap - elements;}
    std::string *begin() const { return elements; } // begin和end成员分别返回指向首元素（即elements）和最后一个构造的元素之后位置（即first_free）的指针。
    std::string *end() const { return first_free; }
    pair<string*, string*> alloc_n_copy(const string *b, const string *e);
    
private:
    std::string *elements;   // 指向数组首元素的指针
    std::string *first_free; // 指向数组第一个空闲元素的指针
    std::string *cap;        // 指向数组尾后位置的指针
    void free();             // 销毁元素并释放内存
    void reallocate();       // 获得更多内存并拷贝已有元素
    static std::allocator<std::string> alloc; // 分配元素
    // 被添加元素函数所使用
    void check_n_alloc() { if(size() == capacity()) reallocate(); }
};
void StrVec::push_back(const std::string &s)
{
    check_n_alloc(); // 确保有空间容纳新元素
    // 在first_free指向的元素中构造s的副本
    alloc.construct(first_free++, s);
    // 当我们用allocator分配内存时，必须记住内存是未构造的（参见12.2.2节，第428页）。
    // 为了使用此原始内存，我们必须调用construct，在此内存中构造一个对象。传递给construct的第一个参数必须是一个指针，指向调用allocate所分配的未构造的内存空间。
    // 剩余参数确定用哪个构造函数来构造对象。在本例中，只有一个额外参数，类型为string，因此会使用string的拷贝构造函数。
    // 值得注意的是，对construct的调用也会递增first_free，表示已经构造了一个新元素。
    // 它使用前置递增（参见4.5节，第131页），因此这个调用会在first_free当前值指定的地址构造一个对象，并递增first_free指向下一个未构造的元素。

    // 前置递增运算符，首先将运算对象+1，然后将改变后的对象作为求值结果。
    // 后置递增运算符，也会将运算对象+1，但是求值结果是运算对象改变之前那个值的副本。
    // int i=0, j;
    // j = ++i;  // j=1, i=1，前置版本得到递增之后的值
    // j = i++;  // j=1, i=2，后置版本得到递增之前的值
}
// alloc_n_copy成员会分配足够的内存来保存给定范围的元素，并将这些元素拷贝到新分配的内存中。
// 此函数返回一个指针的pair（参见11.2.3节，第379页），两个指针分别指向新空间的开始位置和拷贝的尾后的位置：
pair<string*, string*> StrVec::alloc_n_copy(const string *b, const string *e)
{
    // 分配空间保存给定范围中的元素
    auto data = alloc.allocate(e - b); // end - begin
    // 初始化并返回一个pair，该pair由data和uninitialized_copy的返回值构成
    return {data, uninitialized_copy(b, e, data)};
    // 返回的pair的first成员指向分配的内存的开始位置；second成员则是uninitialized_copy（参见12.2.2节，第429页）的返回值，此值是一个指针，指向最后一个构造元素之后的位置。
}
// free成员有两个责任：首先destroy元素，然后释放StrVec自己分配的内存空间。
// for循环调用allocator的destroy成员，从构造的尾元素开始，到首元素为止，逆序销毁所有元素：
void StrVec::free()
{
    // 不能传递给deallocate一个空指针，如果elements为0，函数什么也不做
    if(elements)
    {
        // 逆序销毁旧元素
        for(auto p=first_free; p!=elements; /* 空 */)
            alloc.destroy(--p); // destroy函数会运行string的析构函数。string的析构函数会释放string自己分配的内存空间。
        alloc.deallocate(elements, cap-elements);
        // 一旦元素被销毁，我们就调用deallocate来释放本StrVec对象分配的内存空间。
        // 我们传递给deallocate的指针必须是之前某次allocate调用所返回的指针。因此，在调用deallocate之前我们首先检查elements是否为空。
    }
}
// 拷贝控制成员
StrVec::StrVec(const StrVec &s)
{
    // 调用alloc_n_copy分配空间以容纳与s中一样多的元素
    auto newdata = alloc_n_copy(s.begin(), s.end());
    elements = newdata.first;
    first_free = cap = newdata.second;
    // alloc_n_copy的返回值是一个指针的pair。其first成员指向第一个构造的元素，second成员指向最后一个构造的元素之后的位置。
    // 由于alloc_n_copy分配的空间恰好容纳给定的元素，cap也指向最后一个构造的元素之后的位置。
}
// 析构函数调用free
StrVec::~StrVec() { free(); }
// 拷贝赋值运算符在释放已有元素之前调用alloc_n_copy，这样就可以正确处理自赋值了：
StrVec& StrVec::operator=(const StrVec &rhs)
{
    // 调用alloc_n_copy分配内存，大小与rhs中元素占用空间一样多
    auto data = alloc_n_copy(rhs.begin(), rhs.end());
    free();
    elements = data.first;
    first_free = cap = data.second;
    return *this;
}
// reallocate成员
void StrVec::reallocate()
{
    // 我们将分配当前大小两倍的内存空间，如果StrVec为空，我们将分配容纳一个元素的空间：
    auto newcapacity = size() ? 2*size() : 1;
    // 分配新内存
    auto newdata = alloc.allocate(newcapacity);
    // 将数据从旧内存移动到新内存
    auto dest = newdata;  // 指向新数据中下一个空闲位置？
    auto elem = elements; // 指向旧数组中下一个元素？这不是旧数组中第一个元素吗？
    for(size_t i =0; i!=size(); ++i)
        alloc.construct(dest++, std::move(*elem++));
    free(); // 一旦我们移动完元素就释放旧内存空间
    // 更新我们的数据结构，执行新元素
    elements = newdata;
    first_free = dest;
    cap = elements + newcapacity;

    // 在重新分配内存的过程中移动而不是拷贝元素在编写reallocate成员函数之前，我们稍微思考一下此函数应该做什么。
    // 它应该:1.为一个新的、更大的string数组分配内存 2.在内存空间的前一部分构造对象，保存现有元素 3.销毁原内存空间中的元素，并释放这块内存
    // 由于string的行为类似值，我们可以得出结论，每个string对构成它的所有字符都会保存自己的一份副本。拷贝一个string必须为这些字符分配内存空间，而销毁一个string必须释放所占用的内存。
    // 因此，拷贝这些string中的数据是多余的。在重新分配内存空间时，如果我们能避免分配和释放string的额外开销，StrVec的性能会好得多。

    // 通过使用新标准库引入的两种机制，我们就可以避免string的拷贝。首先，有一些标准库类，包括string，都定义了所谓的“移动构造函数”。
    // 关于string的移动构造函数如何工作的细节，以及有关实现的任何其他细节，目前都尚未公开。但是，我们知道，移动构造函数通常是将资源从给定对象“移动”而不是拷贝到正在创建的对象。
    // 我们使用的第二个机制是一个名为move的标准库函数，它定义在utility头文件中。目前，关于move我们需要了解两个关键点。
    // 首先，当reallocate在新内存中构造string时，它必须调用move来表示希望使用string的移动构造函数，原因我们将在13.6.1节（第470页）中解释。
    // 如果它漏掉了move调用，将会使用string的拷贝构造函数。
    // 其次，我们通常不为move提供一个using声明（参见3.1节，第74页），原因将在18.2.3节（第706页）中解释。当我们使用move时，直接调用std：：move而不是move。
}

int main()
{
    // 13.5 动态内存管理类

    // StrVec类的设计
    // 回忆一下，vector类将其元素保存在连续内存中。为了获得可接受的性能，vector预先分配足够的内存来保存可能需要的更多元素（参见9.4节，第317页）。
    // vector的每个添加元素的成员函数会检查是否有空间容纳更多的元素。如果没有可用空间，vector就会重新分配空间：它获得新的空间，将已有元素移动到新空间中，释放旧空间，并添加新元素。
    // 我们在StrVec类中使用类似的策略。我们将使用一个allocator来获得原始内存（参见12.2.2节，第427页）
    // 由于allocator分配的内存是未构造的，我们将在需要添加新元素时用allocator的construct成员在原始内存中创建对象。
    // 类似的，当我们需要删除一个元素时，我们将使用destroy成员来销毁元素。

    

    
    return 0;
}